//
//  Problem25.swift
//  LeetCode 25 K 个一组翻转链表
//
//  Created by 武侠 on 2020/7/14.
//  Copyright © 2020 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 [25 K 个一组翻转链表]
 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 k 是一个正整数，它的值小于或等于链表的长度。
 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

 示例：
 给你这个链表：1->2->3->4->5
 当 k = 2 时，应当返回: 2->1->4->3->5
 当 k = 3 时，应当返回: 3->2->1->4->5

 说明：
 你的算法只能使用常数的额外空间。
 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

 */
class Problem25: NSObject {
    func solution() {
        let nums = [1, 2, 3, 4, 5]
        if let node = createList(nums) {
            let rnode = reverseKGroup1(node, 3)
            printNode(rnode)
        }
    }
    
    // 方法:
    // 1:   d(0) 1 2 3 4 5 6
    // 2:   d(0) 1 2    3 4 5 6
    // 3:   d(0) 2 1    3 4 5 6
    // 4:   d(0) 2 1 3 4 5 6
    // 5:   d(0) 2 1 3 4    5 6
    // 6:   d(0) 2 1 4 3    5 6
    // 7:   d(0) 2 1 4 3 5 6
    // 8:   d(0) 2 1 4 3 6 5
    func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
        let dumy: ListNode? = ListNode(0)
        dumy?.next = head
        
        var pre = dumy
        var end = dumy
        while end?.next != nil {
            var i = 0
            while i < k, end != nil {
                i += 1
                end = end?.next
            }
            if end == nil {
                break
            }
            
            let start = pre?.next
            let next = end?.next
            end?.next = nil
            pre?.next = backList(start)
            
            start?.next = next
            pre = start
            end = pre
        }
        
        return dumy?.next
    }
    
    
    // 方法二: 先反转前K个, 后面的队列递归
    func reverseKGroup1(_ head: ListNode?, _ k: Int) -> ListNode? {
        let first = head
        var end = head
        var i: Int = 0
        while i < k-1 {
            if end?.next == nil {
                return first
            }
            i += 1
            end = end?.next
        }
        let rnode = reverse(first, end)
        first?.next = reverseKGroup1(first?.next, k)
        return rnode
    }
    
    func reverse(_ head: ListNode?, _ end: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        var fhead = head
        var pro: ListNode? = nil
        
        let endNext = end?.next
        end?.next = nil
        while fhead != nil {
            let next = fhead?.next
            fhead?.next = pro
            pro = fhead
            fhead = next
        }
        head?.next = endNext
        return pro
    }
    
    // 把head反转
    func backList(_ head: ListNode?) -> ListNode? {
        var first = head
        var second: ListNode? = nil     // 第二列的开始
        while first != nil {
            let next = first?.next
            first?.next = second
            second = first
            first = next
        }
        
        
        return second
    }
}
